package 简单.动态规划.其他;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
 * <p>
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/pascals-triangle/
 */
public class 杨辉三角_118 {

    public static void main(String[] args) {

        for (List<Integer> list : generate(4)) {
            System.out.println(list);
        }

    }

    /**
     * 规律：第几行就有几个元素，第一个元素和最后一个元素都为1
     *
     * @param numRows
     * @return
     */
    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> lists = new ArrayList<>();
        for (int curRow = 1; curRow <= numRows; curRow++) {
            List<Integer> curList = new ArrayList<>();
            for (int cur = 1; cur <= curRow; cur++) {
                if (cur == 1 || cur == curRow) {  //首末都为1
                    curList.add(1);
                    continue;
                }
                List<Integer> preList = lists.get(curRow - 1 - 1);  //curRow代表长度，不是索引，需要-1
                curList.add(preList.get(cur - 1) + preList.get(cur - 1 - 1));
            }
            lists.add(curList);
        }
        return lists;
    }

    /**
     * 找规律
     * 第二行开始，第一个数字和最后一个数字都是1
     */
    public List<List<Integer>> generate2(int numRows) {
        List<List<Integer>> lists = new ArrayList<>();
        lists.add(Arrays.asList(1));
        for (int i = 1; i < numRows; i++) {

            List<Integer> curList = new ArrayList<>();
            curList.add(1);

            List<Integer> preList = lists.get(i - 1);
            for (int j = 0; j < preList.size() - 1; j++) {
                curList.add(preList.get(j) + preList.get(j + 1));
            }

            curList.add(1);

            lists.add(curList);
        }

        return lists;
    }

}
